﻿#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<memory.h>
#include <graphics.h>
#include <conio.h>
#define NUM_ALGORITHMS 8

//打印
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

long double swaps1 = 0;
long double compare1 = 0;

//交换
void Swap1(int* x, int* y)//传地址，因此形参是指针（地址）
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
	swaps1++;
}

int Compare1(int a,int b)
{
	compare1++;
	return a - b;

}

//直接插入排序
void InsertSort(int* arr, int n)
{

	for (int i = 0; i < n - 1; i++)
		//注意：这里有一个小坑，我们定义tmp变量，它的位置是在end之后，end最后一个位置如果是n-1，那么tmp就是n越界了会发生报错
	{
		//我们设置两个变量进行比较一下大小
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)//end<0的时候跳出循环
		{
			if (Compare1(arr[end], tmp) > 0)//相等的情况不动，保证排序算法的稳定性
			{

				arr[end + 1] = arr[end];
				swaps1++;
			}
			else
			{
				break;
			}
			end--;
		}
		//当比较到end<0时跳出循环了但是还是没有找到比tmp小的了，于是将tmp交换给arr[end+1],注意此时end=-1,end+1=0是有效位置
		arr[end + 1] = tmp;
		swaps1++;
	}

}


void Print(int* arr, int n, int round)
{
	// 打印“第几趟的排序结果”
	printf("第 %d 趟排序结果: ", round);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void test1()
{
	int n = 10;
	int arr[10] = { 0 };

	// 输入数组的元素
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	// 插入排序
	for (int i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = arr[i];

		// 移动元素以腾出插入位置
		while (end >= 0 && arr[end] > tmp)
		{
			arr[end + 1] = arr[end];
			end--;
		}

		// 插入元素
		arr[end + 1] = tmp;

		// 打印当前每一趟排序的结果，传递当前排序轮次
		Print(arr, n, i);  // i 表示第几趟排序
	}
}



//------------------------------------------------------------

long double swaps2 = 0;
long double compare2 = 0;

//交换
void Swap2(int* x, int* y)//传地址，因此形参是指针（地址）
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
	swaps2++;
}

int Compare2(int a, int b)
{
	compare2++;
	return a - b;

}

//希尔排序
//这是在直接插入排序中的一个优化，它先对一个乱序的数组进行预排序（将数组分成好几次，分别进行排序）
// 当gap==1时就是直接插入排序，此时已经基本有序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)//当gap<=1时，循环结束。这里有一个小坑：gap=1时要跳出循环了，如果循环条件中包含gap==1的情况那么将会进入死循环
		//gap==1时，是在最后一次循环中得到的，比如gap=2,2/3+1=1,然后进行直接插入排序
	{
		gap = gap / 3 + 1;//+1是确保最终gap==1,从而使用直接插入排序
		for (int i = 0; i < n - gap; i++)//i最大取得n-gap-1，保证了end+gai=n-gap-1+gap=n-1不会越界
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (Compare2(arr[end], tmp) > 0)
				{
					arr[end + gap] = arr[end];
					swaps2++;
				}
				else
				{
					break;
				}
				end -= gap;
			}
			arr[end + gap] = tmp;
			swaps2++;
		}
	}

}

void test2() {
	int n = 10;
	int arr[10] = { 0 }; // 初始化数组为零
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]); // 输入数组元素
	}

	int gap = n; // 初始化gap为n
	int round = 1; // 记录排序的轮次
	while (gap > 1)
	{ // 当gap <= 1时，退出循环
		gap = gap / 3 + 1; // 更新gap值

		// 遍历所有的间隔gap进行插入排序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap]; // 临时保存当前元素

			// 对每个分组进行插入排序
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end]; // 需要移动元素
				}
				else
				{
					break; // 已经找到位置，退出循环
				}
				end -= gap; // 移动到下一个位置
			}
			arr[end + gap] = tmp; // 将tmp放入合适的位置
		}

		// 输出当前轮次的排序结果
		printf("第 %d 趟排序结果是: ", round);
		for (int i = 0; i < n; i++)
		{
			printf("%d ", arr[i]);
		}
		printf("\n");

		round++; // 增加轮次计数
	}
}


//-------------------------------------------------------------

long double swaps3 = 0;
long double compare3 = 0;

//交换
void Swap3(int* x, int* y)//传地址，因此形参是指针（地址）
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
	swaps3++;
}

int Compare3(int a, int b)
{
	compare3++;
	return a - b;

}

////直接选择排序
////每次从初始位置开始，遍历到结束位置，符合条件的就交换
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		//下面定义的变量都是数组下面的位置，即数组下标，在比较大小时我们要使用数组进行比较
		int mini = begin;
		int maxi = begin;

		//这里先进行了对最大值与最小值的比较查找，直到找到后再进行交换，避免了过多无效的交换
		for (int i = begin + 1; i <= end; i++)//begin,end分别为起始，结束位置，每过一轮就会少两个数（begin++,end--）
		{
			if (Compare3(arr[i], arr[mini]) < 0)
			{
				mini = i;
				swaps3++;
			}
			if (Compare3(arr[i], arr[maxi]) > 0)
			{
				maxi = i;
				swaps3++;

			}

		}
		//这里防止，maxi就在起始位置，然后交换之后（maxi与mini都会交换一次）maxi仍然在起始位置
		if (maxi == begin)
		{
			maxi = mini;
		}

		Swap3(&arr[mini], &arr[begin]);
		Swap3(&arr[maxi], &arr[end]);
		begin++;
		end--;
	}
}

void test3()
{
	int n = 10;
	int arr[10] = { 0 }; // 初始化数组为零
	// 输入数组元素
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	int round = 0;
	int begin = 0;
	int end = n - 1;

	// 当begin小于end时，继续排序
	while (begin < end)
	{
		int mini = begin;
		int maxi = begin;

		// 查找当前区间内的最小值和最大值
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}

		// 如果最大值的位置恰好在begin，交换最大值和最小值时会影响位置，因此需要调整maxi
		if (maxi == begin)
		{
			maxi = mini;
		}

		// 交换最小值和起始位置的值
		Swap3(&arr[mini], &arr[begin]);
		// 交换最大值和结束位置的值
		Swap3(&arr[maxi], &arr[end]);

		// 输出当前轮次的排序结果
		printf("第 %d 趟排序结果是: ", round);
		for (int i = 0; i < n; i++)
		{
			printf("%d ", arr[i]);
		}
		printf("\n");

		// 更新排序的起始位置和结束位置
		begin++;
		end--;

		// 增加轮次计数
		round++;
	}
}

//-------------------------------------------------------------

long double swaps4 = 0;
long double compare4 = 0;

//交换
void Swap4(int* x, int* y)//传地址，因此形参是指针（地址）
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
	swaps4++;
}

int Compare4(int a, int b)
{
	compare4++;
	return a - b;

}

//向下调整（建造小堆）
void adjustdown(int* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	while (child < n)//当孩子结点超过结点数时就越界了
	{
		//建造小堆：找左右孩子中较小的；
		//建造大堆：找左右孩子中较大的；
		if (child + 1 < n && Compare4(arr[child] ,arr[child + 1])>0)
		{
			child++;
		}
		if (Compare4(arr[child] , arr[parent])<0)
		{
			Swap4(&arr[child], &arr[parent]);
			parent = child;
			swaps4++;
			child = parent * 2 + 1;
			swaps4++;
		}
		//如果那个结点小于其左右孩子，即为一个子树的根节点，符合小堆的性质
		else
		{
			break;
		}
	}
}

//堆排序（降序）
//使用数组建堆，我们将最后一个元素与第一个元素（根结点）交换位置，使用向下调整，最终使得整个树有序，升序/降序
//降序--小堆
//升序--大堆

void HeapSort(int* arr, int n)
{
	//通过向下调整建堆（建小堆/大堆）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)//n-1表示数组中最后一个位置，即新插进来的数据。（n-1-1）/2就是该结点的双亲节点
	{
		adjustdown(arr, i, n);
	}
	//排序
	int end = n - 1;
	while (end > 0)
	{
		Swap4(&arr[0], &arr[end]);//将第一个位置的结点与新插入结点进行交换
		adjustdown(arr, 0, end);
		end--;
	}
}

void test4()
{
	int n = 10;
	int arr[10] = { 0 }; // 初始化数组为零
	// 输入数组元素
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	// 通过向下调整建堆（建小堆）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		adjustdown(arr, i, n);
	}

	// 排序
	int end = n - 1;
	int pass = 1;  // 用来计数排序的趟数
	while (end > 0) {
		// 将第一个位置的结点与新插入结点进行交换
		Swap4(&arr[0], &arr[end]);

		// 向下调整，恢复堆的性质
		adjustdown(arr, 0, end);

		// 输出每一趟排序的结果
		printf("第 %d 趟的排序结果是: ", pass);
		for (int i = 0; i < n; i++) {
			printf("%d ", arr[i]);
		}
		printf("\n");

		end--;  // 排序区域逐渐减少
		pass++;  // 增加排序趟数
	}
}

//-------------------------------------------------------------


long double swaps5 = 0;
long double compare5 = 0;

//交换
void Swap5(int* x, int* y)//传地址，因此形参是指针（地址）
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
	swaps5++;
}

int Compare5(int a, int b)
{
	compare5++;
	return a - b;

}

// 打印
void Print5(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

//快速排序
//本质是一种二叉树排序，通过一个基准值将数组分为两个子序列，然后再对子序列找基准值分子序列，不断递归下去直到排序好

////hoare版本
//int _QuickSort1(int* arr, int left, int right)
//{
//	int keyi = left;//基准值
//	++left;//left指针从基准值后一位开始找
//	while (left<=right)//当两这相等的时候继续找，如果相等就跳出循环.
////这里加上一个等号是因为，交换左右指针只能在两种都找到的时候才能交换。那么这里两个相等，那么这个值大于基准值或者小于基准值
////如果直接交换给基准值，可能导致基准值前面不完全是都小于基准值或者后面不完全是都大于基准值的
//	{
//		
//		//左中找大(在左边找比基准值大的放到后面）
//		while (left <= right && arr[left] < arr[keyi])
//		{
//			left++;
//		}
//		//右中找小（在右边找比基准值小的放到前面）
//		while(left <= right && arr[right] > arr[keyi])
//		{
//			right--;
//		}
//		//只要上面两个都找到了：左边找到大的，右边找到小的，才进行交换
//		if (left <= right)
//		{
//			Swap(&arr[left++], &arr[right --]);
//		}
//	}
//	Swap(&arr[keyi], &arr[right]);
//	return right;
//}

//挖坑法
//int _QuickSort2(int* arr, int left, int right)
//{
//	int hole = left;//定义一个坑，从起始位置开始
//	int keyi = arr[hole];//将第一个坑的位置里面的值用基准值保存下来，方便下一个数填进来，那么就会出现一个新的坑，最后有一个位置放最初的基准值
//	while (left<right)
//	{
//		//注意：keyi是arr[hole]，已经是一个数组了，不用再套一个数组了
//		//左中找大
//		while (left < right && arr[left] < keyi)
//		{
//			++left;
//		}
//		//找到后将这个值填入坑中
//		arr[hole] = arr[left];
//		hole=left;//此时变成了一个新的坑
//
//		//右中找小
//		while (left<right && arr[right]>keyi)
//		{
//			--right;
//		}
//		arr[hole] = arr[right];
//		hole = right;
//	
//	}//跳出循环，则说明基本排序好了，还剩下一个坑用来填最初的基准值
//	arr[hole] = keyi;
//	return hole;//返回hole的位置，即基准值的位置
//
//}
//
// 
//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{
	int keyi = left;//设立一个基准值放在起始位置
	int prev = left, cur = left + 1;//再设置两个指针进行比较交换排序
	while (cur <= right)
	{
		//找到比基准值小的，排在基准值的左边，注意：我们要从第二个位置开始进行比较交换，不要改变基准值
		while (Compare5(arr[cur] ,arr[keyi])<0 && ++prev != cur)
			//++prev的意思是，prev先往前走一步，再加上++prev != cur，是防止两个指针都停在一个位置，于是如果在同一位置，++prev不执行(跳出循环了），cur++
			//那么这两个指针分别从第二个，第三个位置开始
		{
			Swap5(&arr[prev], &arr[cur]);
		}
		++cur;
	}
	Swap5(&arr[keyi], &arr[prev]);
	return prev;//返回prev的位置，此时这个位置放置的是基准值
}

void QuickSort(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int keyi = _QuickSort(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}


int step5 = 1;

// Lomuto前后指针法
int _QuickSort1(int* arr, int left, int right, int* step5)
{
	int keyi = left; // 设立一个基准值放在起始位置
	int prev = left, cur = left + 1; // 再设置两个指针进行比较交换排序
	while (cur <= right)
	{
		// 找到比基准值小的，排在基准值的左边，注意：我们要从第二个位置开始进行比较交换，不要改变基准值
		while (Compare5(arr[cur], arr[keyi]) < 0 && ++prev != cur)
		{
			Swap5(&arr[prev], &arr[cur]);
		}
		++cur;
	}
	Swap5(&arr[keyi], &arr[prev]);
	// 打印当前这趟的排序结果
	printf("第 %d 趟排序结果是：", (*step5)++);
	Print5(arr, right + 1);

	return prev; // 返回prev的位置，此时这个位置放置的是基准值
}

// 快速排序
void QuickSort1(int* arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int keyi = _QuickSort1(arr, left, right, &step5);
	QuickSort1(arr, left, keyi - 1);
	QuickSort1(arr, keyi + 1, right);
}

void test5()
{
	int a[10] = { 0 };
	int n = sizeof(a) / sizeof(a[0]);
	//printf("请输入10个整数：\n");
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]); // 移除多余的空格
	}


	QuickSort1(a, 0, n - 1);

	printf("排序后的数组是：");
	Print5(a, n);
}


//-------------------------------------------------------------


long double swaps6 = 0;
long double compare6 = 0;

//交换
void Swap6(int* x, int* y)//传地址，因此形参是指针（地址）
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
	swaps6++;
}

int Compare6(int a, int b)
{
	compare6++;
	return a - b;

}

//打印
void Print6(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}


//归并排序的一个子函数，
// 用来对序列进行分治操作（分：不断递归地分割序列，使得最后每个数组中只有一个数据为止；治：对数组进行局部排序并合并）
void _MergeSort(int* arr, int left, int right, int* tmp)
{
	int step = 0;
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;
	//将上面数组中的序列进行分割
	//[left,mid],[mid+1,right]
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid + 1, right, tmp);

	//对两个有序序列进行合并
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	int index = begin1;//定义一个变量表示数组的下标，便于等会两个序列插入到一个数组中
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (Compare6(arr[begin1] ,arr[begin2])<0) //哪组数据中的数据小就让将哪个放到数组中
		{
			tmp[index++] = arr[begin1++];
			swaps6++;
		}
		else
		{
			tmp[index++] = arr[begin2++];
			swaps6++;

		}

	}
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
		swaps6++;

	}

	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
		swaps6++;

	}

	//将我们tmp数组中的数据放到arr数组中
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
		swaps6++;

	}

}


//归并排序
void MergeSort(int* arr, int n)
{
	//申请一个数组的空间，用来存放排序好的序列
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	_MergeSort(arr, 0, n - 1, tmp);
	_MergeSort(arr, 0, n - 1, tmp);
	//动态申请的数组释放
	free(tmp);
	tmp = NULL;

}


void _MergeSort1(int* arr, int left, int right, int* tmp, int* step)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;

	// 递归分割
	_MergeSort1(arr, left, mid, tmp, step);
	_MergeSort1(arr, mid + 1, right, tmp, step);

	// 合并两个有序的子数组
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;

	int index = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (Compare6(arr[begin1], arr[begin2]) < 0)
		{
			tmp[index++] = arr[begin1++];
		}
		else
		{
			tmp[index++] = arr[begin2++];
		}
		// 注意：这里不应该增加swaps6，因为比较不代表交换
	}

	// 将剩余的元素放入tmp数组
	while (begin1 <= end1)
	{
		tmp[index++] = arr[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[index++] = arr[begin2++];
	}

	// 将tmp数组中的数据放回arr数组中
	for (int i = left; i <= right; i++)
	{
		arr[i] = tmp[i];
	}

	// 打印当前这趟的排序结果
	printf("第 %d 趟排序结果是：", (*step)++);
	Print6(arr, right + 1);
}

// 归并排序的外部接口
void MergeSort1(int* arr, int n)
{
	// 创建临时数组
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}

	// 使用一个计数器来记录排序的趟数
	int step = 1;
	_MergeSort1(arr, 0, n - 1, tmp, &step);

	// 释放临时数组
	free(tmp);
}

// 测试函数
void Test6()
{
	int arr[10] = { 0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < n; i++) // 修改为读取全部10个整数
	{
		scanf("%d", &arr[i]); // 移除多余的空格
	}

	printf("原始数组是：");
	Print6(arr, n);

	MergeSort1(arr, n);

	printf("排序后的数组是：");
	Print6(arr, n);
}

//-------------------------------------------------------------

long double swaps7 = 0;
long double compare7 = 0;

//交换
void Swap7(int* x, int* y)//传地址，因此形参是指针（地址）
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
	swaps7++;
}

int Compare7(int a, int b)
{
	compare7++;
	return a - b;

}


//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)//外层循环：遍历的趟数
	{
		int exchange = 0;//（exchang=0表示没有进行交换，exchange=1表示进行交换了）
		//这是我们设置的一个标志量，我们再在交换的地方修改标志量的值，最后我们再根据标志量是否变化来判断排序是否提前结束

		for (int j = 0; j < n - i - 1; j++)//内存循环：每趟遍历的情况
			//由于i++,就是进入了不同的循环，由于每循环一次就排好了一个数（一个数字像气泡一样冒上去），于是总数减去冒泡的趟数就是该次循环要遍历的次数
			//在循环中，我们进行了一个arr[j]与arr[j+1]的比较，因此j的上限要-1，那么j+1就不会越界了
		{
			if (Compare7(arr[j] ,arr[j + 1])>0)
			{
				exchange = 1;//如果没进入交换，则说明是有序的，那么提前结束循环
				Swap7(&arr[j], &arr[j + 1]);
			}
		}
		//有时候break会导致其可维护性变差，代码混乱等问题，因此我们可以将判断序列是否提前有序的标志量放到循环条件中来进行对代码的提前结束
		if (exchange == 0)
		{
			break;
		}
	}
}


//void BubbleSort2(int* arr, int n)
//{
//	int exchange = 1;//exchange=1表示进行交换了，exchange=0表示没有进行交换
//	for (int i = 0; i < n && exchange == 1; i++)//初始化exchange时要将exchange置为1，否则它将进入不了循环中
//	{
//		exchange = 0;
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				exchange = 1;
//				Swap(&arr[j], &arr[j + 1]);
//			}
//		}
//	}
//}


void test7() {
	int n = 10;
	int arr[10] = { 0 };

	// 输入数组元素
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}

	// 外层循环：遍历的趟数
	for (int i = 0; i < n; i++)
	{
		int exchange = 0; // 标志量，表示是否有交换

		// 内层循环：每趟遍历的情况
		for (int j = 0; j < n - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				exchange = 1; // 有交换，设置标志量
				Swap7(&arr[j], &arr[j + 1]);
			}
		}

		// 输出每一趟排序后的数组
		printf("第 %d 趟的排序结果是：", i + 1);
		for (int k = 0; k < n; k++)
		{
			printf("%d ", arr[k]);
		}
		printf("\n");

		// 如果没有交换，提前结束排序
		if (exchange == 0) {
			break;
		}
	}
}


//-------------------------------------------------------------
long double swaps8 = 0;
long double compare8 = 0;

//交换
void Swap8(int* x, int* y)//传地址，因此形参是指针（地址）
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
	swaps8++;
}

int Compare8(int a, int b)
{
	compare8++;
	return a - b;

}


//计数排序
void CountSort(int* arr, int n)
{
	int min = arr[0];
	int max = arr[0];
	for (int i = 1; i < n; i++)//从数组下标1开始遍历，arr[0]位置放着min与max
	{
		if (Compare8(arr[i], max)>0)
		{
			max = arr[i];
			swaps8++;
		}
		if (Compare8(arr[i] ,min)<0)
		{
			min = arr[i];
			swaps8++;

		}
	}
	int range = max - min + 1;
	//创建一个数组，数组的下标表示的是数据值（实际值-min)，数组中是该数据重复出现的次数
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}

	memset(count, 0, range * sizeof(int));//这个函数是用来是动态申请的空间中所有内容都置为0，需要头文件#include<memory.h>

	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;//将原数组中的数减去最小值就映射到count数组中的位置
	}

	//通过count数组来进行排序
	int index = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)//每个数据都打印下来
		{
			arr[index++] = min + i;
		}
	}

}

void PrintArray(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void test8()
{
	int n = 10;
	int arr[10] = { 0 };

	// 输入数组元素
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	int min = arr[0];
	int max = arr[0];

	// 找到最小值和最大值
	for (int i = 1; i < n; i++) {
		if (arr[i] > max) {
			max = arr[i];
		}
		if (arr[i] < min) {
			min = arr[i];
		}
	}

	int range = max - min + 1;

	// 创建一个计数数组，大小为值域范围
	int* count = (int*)malloc(sizeof(int) * range);
	if (count == NULL) {
		perror("malloc fail!");
		exit(1);
	}

	memset(count, 0, range * sizeof(int)); // 初始化计数数组为0

	// 统计原数组中每个数的出现次数
	for (int i = 0; i < n; i++) {
		count[arr[i] - min]++;
	}

	int index = 0;
	int pass = 1;  // 记录当前是第几趟排序

	// 根据计数数组排序，并打印每一趟的结果
	for (int i = 0; i < range; i++)
	{
		while (count[i]--) {
			arr[index++] = min + i;
		}
		// 输出每一趟排序结果
		printf("第 %d 趟的排序结果是: ", pass++);
		PrintArray(arr, n);
	}

	free(count);  // 释放动态分配的内存
}


//----------------------------------------------------------------------------------------------------------------

void TestO()
{
	srand(time(0));
	const int N = 100000;


	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	int* a7 = (int*)malloc(sizeof(int) * N);
	int* a8 = (int*)malloc(sizeof(int) * N);


	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand() + i;
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
		a7[i] = a1[i];
		a8[i] = a1[i];
	}


	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();

	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();

	int begin7 = clock();
	BubbleSort(a7, N);
	int end7 = clock();

	int begin8 = clock();
	CountSort(a8, N);
	int end8 = clock();



	int ret1 = end1 - begin1;
	int ret2 = end2 - begin2;
	int ret3 = end3 - begin3;
	int ret4 = end4 - begin4;
	int ret5 = end5 - begin5;
	int ret6 = end6 - begin6;
	int ret7 = end7 - begin7;
	int ret8 = end8 - begin8;
	printf("以下是八大排序算法的排序时间(单位：ms):\n");
	printf("InsertSort:%d\n", ret1);
	printf("ShellSort:%d\n", ret2);
	printf("SelectSort:%d\n", ret3);
	printf("HeapSort:%d\n", ret4);
	printf("QuickSort:%d\n", ret5);
	printf("MergeSort:%d\n", ret6);
	printf("BubbleSort:%d\n", ret7);
	printf("CountSort:%d\n", ret8);
	printf("\n");
	printf("-------------------------------------------------------------------------\n");
	printf("以下是八大排序算法的交换，比较次数(单位：次）：\n");
	printf("%-12s%-15s%-15s\n", "算法名称", "交换次数", "比较次数"); 
	printf("%-12s%-15.1Lf%-15.1Lf\n", "InsertSort", swaps1, compare1);
	printf("%-12s%-15.1Lf%-15.1Lf\n", "ShellSort", swaps2, compare2);
	printf("%-12s%-15.1Lf%-15.1Lf\n", "SelectSort", swaps3, compare3);
	printf("%-12s%-15.1Lf%-15.1Lf\n", "HeapSort", swaps4, compare4);
	printf("%-12s%-15.1Lf%-15.1Lf\n", "QuickSort", swaps5, compare5);
	printf("%-12s%-15.1Lf%-15.1Lf\n", "MergeSort", swaps6, compare6);
	printf("%-12s%-15.1Lf%-15.1Lf\n", "BubbleSort", swaps7, compare7);
	printf("%-12s%-15.1Lf%-15.1Lf\n", "CountSort", swaps8, compare8);




	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
	free(a7);
	free(a8);



	//------------------------------------------------------
	// 排序算法名称
	const char* algorithms[NUM_ALGORITHMS] =
	{
		"InsertSort", "ShellSort", "SelectSort", "HeapSort",
		"QuickSort", "MergeSort", "BubbleSort", "CountSort"
	};


	// 每个排序算法的执行时间（单位：ms）
	int times[NUM_ALGORITHMS] = { ret1, ret2, ret3, ret4, ret5, ret6, ret7, ret8 };

	// 图形窗口的宽度和高度
	const int WINDOW_WIDTH = 800;
	const int WINDOW_HEIGHT = 600;

	// 最大排序时间，用于调整柱状图的缩放
	int maxTime = 5000;

	// 创建一个图形窗口
	initgraph(WINDOW_WIDTH, WINDOW_HEIGHT);

	// 设置坐标轴
	setlinecolor(WHITE);
	line(50, 350, 50, 50);  // Y轴
	line(50, 350, 550, 350); // X轴

	// 绘制柱状图
	int barWidth = 50; // 每个柱子的宽度
	int space = 20;    // 每个柱子之间的间隔

	for (int i = 0; i < NUM_ALGORITHMS; i++) {
		// 每个柱子的位置
		int x = 60 + i * (barWidth + space);
		// 根据最大排序时间来调整每个柱子的高度
		int barHeight = (times[i] * 300) / maxTime; // 缩放，最大高度为 300

		// 绘制柱子
		setfillcolor(RGB(0, 0, 255)); // 设置柱子颜色为蓝色
		fillrectangle(x, 350 - barHeight, x + barWidth, 350); // 绘制矩形（柱子）

		// 在柱子上方绘制时间
		char timeStr[10];
		sprintf(timeStr, "%d", times[i]);
		outtextxy(x + barWidth / 4, 350 - barHeight - 20, timeStr);

		// 绘制排序算法名称
		outtextxy(x + barWidth / 4, 360, algorithms[i]);
	}

	// 显示柱状图
	_getch();
	closegraph(); // 关闭图形窗口
}





void smallMenu1() {
	int input;

	while (1) {
		printf("     *************************************************************\n");
		printf("     *                                                           *\n");
		printf("     *                   1. 展现排序效率                         *\n");
		printf("     *                   2. 返回大菜单                           *\n");
		printf("     *                                                           *\n");
		printf("     *************************************************************\n");

		printf("请输入你的选择: ");
		scanf("%d", &input);

		switch (input)
		{
		case 1:
			printf("\n");
			TestO();
			break;
		case 2:
			printf("返回大菜单。\n");
			return;
		default:
			printf("无效选择，请重新输入。\n");
		}
	}
}

// 小菜单2的功能
void smallMenu2()
{
	int choice;

	while (1) 
	{

		printf("*************************************************************\n");
		printf("                    八大排序算法排序过程 :                    \n");
		printf("*************************************************************\n");
		printf("  1. InsertSort (直接插入排序) 的排序过程                   \n");
		printf("  2. ShellSort (希尔排序) 的排序过程                       \n");
		printf("  3. SelectSort (直接选择排序) 的排序过程                   \n");
		printf("  4. HeapSort (堆排序) 的排序过程                         \n");
		printf("  5. QuickSort (快速排序) 的排序过程                       \n");
		printf("  6. MergeSort (归并排序) 的排序过程                       \n");
		printf("  7. BubbleSort (冒泡排序) 的排序过程                      \n");
		printf("  8. CountSort (计数排序) 的排序过程                       \n");
		printf("  9. 返回大菜单                                            \n");
		printf("*************************************************************\n");

		printf("请输入你的选择: ");
		scanf("%d", &choice);

		switch (choice) 
		{
		case 1:
			printf("请输入10个数字:\n");
			test1();
			break;
		case 2:
			printf("请输入10个数字:\n");
			test2();
			break;
		case 3:
			printf("请输入10个数字:\n");
			test3();
			break;
		case 4:
			printf("请输入10个数字:\n");
			test4();
			break;
		case 5:
			printf("请输入10个数字:\n");
			test5();
			break;
		case 6:
			printf("请输入10个数字:\n");
			Test6();
			break;
		case 7:
			printf("请输入10个数字:\n");
			test7();
			break;
		case 8:
			printf("请输入10个数字:\n");
			test8();
			break;
		case 9:
			printf("返回大菜单。\n");
			return;
		default:
			printf("无效选择，请重新输入。\n");
		}
	}
}

// 大菜单的功能
void bigMenu()
{
	int choice;

	while (1)
	{
		printf("-----------------------------------------------   \n");
		printf("   八大排序算法效率比较及具体展示     \n");
		printf("  1.八大排序算法的效率比较及交换比较次数  \n");
		printf("  2.各种排序算法排序过程  \n");
		printf("  3. 退出程序\n");
		printf("-----------------------------------------------   \n");

		printf("请输入你的选择: ");
		scanf("%d", &choice);

		switch (choice) 
		{
		case 1:
			// 调用小菜单1
			smallMenu1();
			break;
		case 2:
			// 调用小菜单2
			smallMenu2();
			break;
		case 3:
			// 退出程序
			printf("退出程序。\n");
			return;
		default:
			printf("无效选择，请重新输入。\n");
		}
	}
}

int main()
{
	// 启动大菜单
	bigMenu();
	return 0;
}
